package com.bjsxt.datastructure.search;

import com.bjsxt.datastructure.linetable.List;

import java.util.ArrayList;

/**
 * 在分数中查找指定分数
 */
public class TestSearch1 {
    static int myPosition = 0;
    public static void main(String[] args) {
        myPosition = 3;
        System.out.println(myPosition);
        //给定分数的数组
        int[] scoreList = {1, 3, 5, 99, 34, 56, 32, 78, 89};
        int[] scoreList2 = new int[]{1, 3, 5, 32, 34, 56, 78, 89, 99};
        //给定需要查找的分数
        int myScore = 78;
        //查找分数

//        //顺序查找
//        int position = getScore(scoreList, myScore);
//        //二分法查找
//        int position2 = getTwoScore(scoreList2, myScore);
//
//        //输出结果
//        System.out.println("顺序查找法，给定分数的位置是：" + position);
//        System.out.println("二分查找法，给定分数的位置是：" + position2);
    }

    private static int getScore(int[] scoreList, int score) {
        if (scoreList != null && scoreList.length > 0) {
            for (int i = 0; i < scoreList.length; i++) {
                if (scoreList[i] == score) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 二分法查找
     */
    private static int getTwoScore(int[] scoreList, int score) {

        if (scoreList != null && scoreList.length > 1) {
            int position = scoreList.length / 2;
            myPosition = position + myPosition;
            if (scoreList[position] == score) {
                return myPosition;
            } else if (scoreList[position] < score) {
                getTwoScore(getList1(scoreList, position), score);
            } else {
                getTwoScore(getList2(scoreList, position), score);
            }

        } else {
            return -1;
        }
        return myPosition;

    }

    private static int[] getList1(int[] list, int position) {
        int[] c = new int[list.length - position];
        for (int i = 0; i < list.length - position; i++) {
            c[i] = list[i + position];
        }
        return c;
    }

    private static int[] getList2(int[] list, int position) {
        int[] c = new int[position];
        for (int i = 0; i < position; i++) {
            c[i] = list[i];
        }
        return c;
    }
}
